package org.liaohailong.helloworld.stack;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * Author: liaohailong
 * Time: 2021/5/24 11:43
 * Describe:
 */
public class DesignKey {

    // LC 字母异位词分组
//    public List<List<String>> groupAnagrams(String[] strs) {
//        HashMap<String, Integer> hashMap = new HashMap<>();
//        List<List<String>> list = new LinkedList<>();
//
//        for (String str : strs) {
//            char[] chars = str.toCharArray();
//            Arrays.sort(chars);
//            String sort = String.valueOf(chars);
//            Integer integer = hashMap.get(sort);
//            if (integer != null) {
//                List<String> res = list.get(integer);
//                res.add(str);
//            } else {
//                int index = list.size();
//                LinkedList<String> res = new LinkedList<>();
//                res.add(str);
//                list.add(res);
//                hashMap.put(sort, index);
//            }
//        }
//
//        return list;
//    }

    // LC 有效的数独
    public boolean isValidSudoku(char[][] board) {
        HashSet<Character> hashSet = new HashSet<>();
        // 所有行是否无效
        for (int i = 0; i < 9; i++) {
            hashSet.clear();
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                if (hashSet.contains(board[i][j])) {
                    return false;
                } else hashSet.add(board[i][j]);
            }
        }
        // 所有列是否无效
        for (int i = 0; i < 9; i++) {
            hashSet.clear();
            for (int j = 0; j < 9; j++) {
                if (board[j][i] == '.') continue;
                if (hashSet.contains(board[j][i])) {
                    return false;
                } else hashSet.add(board[j][i]);
            }
        }
        // 所有3x3宫格内是否出现重复数字
        int i = 0;
        int j = 0;
        while (true) {
            if (!isValidSudoku(board, i, j, hashSet)) return false;
            i += 3;
            if (i >= 9) {
                i = 0;
                j += 3;
            }
            if (j >= 9) break;
        }

        return true;
    }

    private boolean isValidSudoku(char[][] board, int x, int y, HashSet<Character> hashSet) {
        hashSet.clear();
        for (int i = x; i < x + 3; i++) {
            for (int j = y; j < y + 3; j++) {
                if (board[j][i] == '.') continue;
                if (hashSet.contains(board[j][i])) {
                    return false;
                } else hashSet.add(board[j][i]);
            }
        }
        return true;
    }

    Map<String, Integer> map = new HashMap<>();
    List<TreeNode> res = new LinkedList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traversal(root);
        return res;
    }

    private String traversal(TreeNode root) {
        if (root == null) return "#";
        String key = root.val + "-" + traversal(root.left) + "-" + traversal(root.right);
        Integer count = map.get(key);
        map.put(key, count == null ? 1 : count + 1);
        count = map.get(key);
        if (count != null && count == 2) res.add(root);
        return key;
    }


    private static final class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
